#include <iostream>
#include <vector>
#include <stack>
#include <map>

using namespace std;

// Topological Sorting
class Solution
{
public:
    bool canFinish(int numCourses, vector<vector<int>> &prerequisites)
    {
        map<int, pair<int, vector<int>>> degrees; // index,in,out
        for (int i = 0; i < numCourses; i++)
        {
            degrees[i] = {0, {}};
        }
        for (int i = 0; i < prerequisites.size(); i++)
        {
            int from = prerequisites[i][1];
            int to = prerequisites[i][0];
            degrees[to].first++;
            degrees[from].second.push_back(to);
        }

        stack<int> zeroStack;
        for (auto it = degrees.begin(); it != degrees.end(); it++)
        {
            if (it->second.first == 0)
            {
                zeroStack.push(it->first);
            }
        }
        while (!zeroStack.empty())
        {
            int cur = zeroStack.top();
            zeroStack.pop();
            for (auto out : degrees[cur].second)
            {
                degrees[out].first--;
                if (degrees[out].first == 0)
                {
                    zeroStack.push(out);
                }
            }
        }
        for (auto it = degrees.begin(); it != degrees.end(); it++)
        {
            if (it->second.first != 0)
            {
                return false;
            }
        }
        return true;
    }
};

int main()
{
    cout << "Code207" << endl;
    Solution s;
    return 0;
}

/* memory friendly
bool canFinish(int numCourses, vector<vector<int>> &prerequisites)
{
    map<int, int> inDegree;
    for (int i = 0; i < numCourses; i++)
    {
        inDegree[i] = 0;
    }
    for (int i = 0; i < prerequisites.size(); i++)
    {
        inDegree[prerequisites[i][0]]++;
    }

    stack<int> zeroStack;
    for (auto it = inDegree.begin(); it != inDegree.end(); it++)
    {
        if (it->second == 0)
        {
            zeroStack.push(it->first);
        }
    }
    while (!zeroStack.empty())
    {
        int cur = zeroStack.top();
        zeroStack.pop();
        for (int i = 0; i < prerequisites.size(); i++)
        {
            if (prerequisites[i][1] == cur)
            {
                inDegree[prerequisites[i][0]]--;
                if (inDegree[prerequisites[i][0]] == 0)
                {
                    zeroStack.push(prerequisites[i][0]);
                }
            }
        }
    }
    for (auto it = inDegree.begin(); it != inDegree.end(); it++)
    {
        if (it->second != 0)
        {
            return false;
        }
    }
    return true;
}
*/